package loengud.w10;

public class BinarySearch {
	public static final int KEY_NOT_FOUND = -1;
	public static void main(String[] args) {
		int[] a = {1, 2, 3, 4, 5, 10, 12};
		System.out.println(binarySearch(a, 5, 0, a.length - 1));
	}
	
	public static int binarySearch(int[] a, int searchValue, int left, int right) {
		System.out.println(searchValue + ", " + left + ", " + right);
		if (left > right) {
			return KEY_NOT_FOUND;
		}
		// middle index
		int mid = (left + right) / 2;
		if (a[mid] < searchValue) {
			// searched value is in upper subset
			return binarySearch(a, searchValue, mid + 1, right);
		} else if (a[mid] > searchValue) {
			// searched value is in lower subset
			return binarySearch(a, searchValue, left, right - 1);
		} else {
			// we have found the searchValue
			return mid;
		}
	}
}
